﻿#pragma once
//Common.h  集成通用资源
#include<iostream>
#include<vector>
#include<time.h>
#include<assert.h>
#include<algorithm>
#include<mutex>
#include<thread>
#include<unordered_map>
#include <atomic>

//#include "ObjectPool.h"

//减少宏的使用  容易出问题  难调试
//#define MAXFL 208
//#define MAXBYTES 256*1024

//ThreadCache桶的长度
static const size_t NFL = 208;
//单次申请最大内存
static const size_t MAX_BYTES = 256 * 1024;
//用于计算页号和页起始地址   单页8Kb  2的13次方  13位 地址右移13位得页号 页号左移13位得地址
static const size_t PAGE_SHIFT = 13;
// page cache 管理span list哈希表⼤⼩ 129是因为从1开始计算桶
static const size_t NP = 129;

//不同系统  不同系统调用 不同头文件
#ifdef _WIN32
#include<windows.h>
#else
//linux等系统 此处暂不展开
#endif 

//Page_ID  32位系统/64位系统
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#else
typedef size_t PAGE_ID;
#endif

////size_t 在32位系统 unsigned int  64位系统 unsigned long
//typedef size_t PAGE_ID;

using std::cout;
using std::endl;

//用系统调用申请内存
//windows VirtualAlloc()  linux brk() 和mmap()
inline static void* SystemAlloc(size_t kpage)
{

#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);//可能会出现空间不够的情况
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

//释放
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

//获取链表节点的next节点地址
//用内存块头部存下一个节点的地址
//这里连接的就是空间，内存块与内存块直接互相连接起来形成一个链表
static void*& Next(void* node)
{
	return *(void**)node;
}

//空闲链表
class Freelist
{
public:
	//单个插入
	void Push(void* node)
	{
		assert(node);
		//头插
		Next(node) = _freelist;
		_freelist = node;
		++_size;
	}
	//批量插入
	void PushRange(void* start, void* end,size_t n)
	{
		Next(end) = _freelist;
		_freelist = start;
		_size += n;
	}
	//单个删除
	void* Pop()
	{
		//头删
		assert(_freelist);
		void* ret = _freelist;
		_freelist = Next(ret);
		
		--_size;
		return ret;
	}
	//批量删除
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);

		start = _freelist;
		end = start;
		
		for(size_t i = 0;i<n-1;++i)
		{
			//assert(Next(end));
			end = Next(end);
		}

		_freelist = Next(end);
		Next(end) = nullptr;
		_size -= n;
	}
	bool Empty()
	{
		return _freelist == nullptr;
	}

	size_t Size()
	{
		return _size;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

private:
	void* _freelist = nullptr;//链
	size_t _size = 0;    //链上现有内存块
	size_t _maxSize = 1; //单次最大内存块申请数量
};

//哈希映射类  
//1 长度对齐 - 方便映射 - 方便开辟对齐划分 - 产生内碎片
//2.找是哪个桶的 
// 管理对⻬和映射等关系
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎⽚浪费
	// [1,128] 8byte对⻬ freelist[0,16)
	// [128+1,1024] 16byte对⻬ freelist[16,72)
	// [1024+1,81024] 128byte对⻬ freelist[72,128)
	// [8*1024+1,641024] 1024byte对⻬ freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对⻬ freelist[184,208)
	static inline size_t _RoundUp(size_t bytes, size_t align)
	{
		//位运算实现对齐逻辑
		// 举个例子  按8字节对齐  1 2 3 4 都要对齐到8  对于1 要+7 2要+6 3要+5 与其计算要加多少  不如直接+7 多的减去 
		//用位运算就很容易实现 例  3+7  0011+0111 = 1010  ~(8 - 1)= 1000 1010&1000 = 1000 对齐到了8
		return (((bytes)+align - 1) & ~(align - 1));
	}
	// 对⻬⼤⼩计算
	static inline size_t RoundUp(size_t bytes)
	{
		if (bytes <= 128) {
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024) {
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8 * 1024) {
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 64 * 1024) {
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024) {
			return _RoundUp(bytes, 8 * 1024);
		}
		else {
			return _RoundUp(bytes, 1 << PAGE_SHIFT);
		}
		return -1;
	}
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		//位运算实现映射位置计算逻辑
		//(bytes + (1 << align_shift) - 1)其中align_shift 移位数
		// 逻辑类似上面“直接+7 多的减去” 举个例子  3应该映射到0号位置 这里 3 + 7 得1010（二进制） 右移3位为1 -1得0
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	// 计算映射的哪⼀个⾃由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 81024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] +
				group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}
	// 计算⼀次从中⼼缓存获取多少个内存块
	static size_t NumBatch(size_t size)
	{
		if (size == 0)
			return 0;
		//直接按最多的情况来
		int num = MAX_BYTES / size;
		//范围[2, 512]
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}

	// 计算⼀次向系统获取⼏个⻚
	// 单个对象 8byte 1页
	// ...
	// 单个对象 256KB 32页
	// 
	static size_t NumPage(size_t size)
	{
		//一批获取几个？
		size_t num = NumBatch(size);
		//总大小？
		size_t npage = num * size;
		//对应页数？
		//1 8B >> 13 = 0
		//1 8Kb >> 13 = 1
		npage >>= PAGE_SHIFT;
		//最少1页
		if (npage == 0)
			npage = 1;
		return npage;
	}
};

struct Span
{
	PAGE_ID _pageid = 0; //首页页号
	size_t _n = 0;       //页数

	//双向链表前后指针
	Span* _next = nullptr;
	Span* _prev = nullptr;

	bool isUse = false;//使用标志
	size_t _objSize = 0;//内存块大小

	size_t _useCount = 0;//Span分配出去的内存数 0表示该span完全空闲
	void* _freelist = nullptr;//链
};

//双向带头循环列表
class SpanList
{
	Span* _head = nullptr;
	
public:
	std::mutex _mtx;
	//初始化
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	//返回首尾节点
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	// 判空
	bool Empty()
	{
		return _head->_next == _head;
	}
	//头插头删
	void PushFront(Span* node)
	{
		Insert(Begin(), node);
	}
	Span* PopFront()
	{
		Span* ret = _head->_next;
		Erase(ret);
		return ret;
	}
	//插入删除
	void Insert(Span* pos,Span* node)
	{
		assert(pos);
		assert(node);

		Span* prev = pos->_prev;
		// prev newspan pos
		prev->_next = node;
		node->_prev = prev;
		node->_next = pos;
		pos->_prev = node;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;

	}
};